/*
 * Copyright 北京航空航天大学 @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <p>
 * 寻找组合和 比如 输入： 正整数序列{2,3,4,7} ，正目标值为7 
 * 输出：{7}，{2,2,3}，{3,4} 
 * 要求：每个组合的元素按照升序排列，每个元素可以出现多次
 * </p>
 * 
 * @author towan
 * @Email tongwenzide@163.com 2015年5月24日
 * @version V1.0
 */
public class CombinationSum {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        //边界判断
        if(candidates==null || target<0){
            return result;
        }
        Arrays.sort(candidates);
        int len = candidates.length;
        //非正数判断
        if(candidates[0]<0 || candidates[len-1]<0){
            return result;
        }
        
        List<Integer> path = new ArrayList<Integer>();
        
        findCombinationSum(candidates, 0 ,target, path, result);
        
        return result;
    }

    /**
     * 查询组合和
     * @param candidates
     * @param start
     * @param target
     * @param path
     * @param result
     * @author towan
     * @Email  tongwenzide@163.com
     * 2015年5月24日
     */
    private void findCombinationSum(int[] candidates, int start, int target, List<Integer> path,
            List<List<Integer>> result) {
        if(target<0){
            return;
        }
        //找到一个结果
        if(target == 0){
            result.add(new ArrayList<Integer>(path));
        }else{//递归寻找
            for(int i=start;i<candidates.length;i++){
                if(candidates[i]>target){
                    break;//后面的数肯定都比目标值大
                }
                path.add(candidates[i]);
                //查找结果
                findCombinationSum(candidates, i, target-candidates[i], path, result);
                //重置
                path.remove(path.size()-1);
            }
        }
        
    }
    
    public static void main(String[] args) {
        CombinationSum combin = new CombinationSum();
        int[] candidates = {2,3,6,7};
        int target = 7;
        List<List<Integer>> combinationSum = combin.combinationSum(candidates, target);
        System.out.println(combinationSum);
    }
}
